package org.example;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

// 回溯算法
public class Permute {
    List<List<Integer>> res = new LinkedList<>();

    /*主函数，输入一组不重复的数字，返回他们的全排列*/
    List<List<Integer>> permute(int[] nums){
        // 记录“路径”
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    // 路径：记录在track中
    // 选择列表：nums中不存在于track的那些元素
    // 结束条件：nums中的元素全都在track中出现
    void backtrack(int[] nums, LinkedList<Integer> track){
        // 触发结束条件
        if (track.size() == nums.length){
            res.add(new LinkedList<>(track));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            // 排除不合法的选择
            if (track.contains(nums[i])){
                continue;
            }
            // 做选择
            track.add(nums[i]);
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }
}

class NQueen{
    String[][] res;

    String[][] solveNQueens(int n){
        // .表示空，Q表示皇后，初始化空棋盘
        String[] board = new String[n];
        Arrays.fill(board, ".");
        backtrack(board, 0);
        return res;
    }

    // 路径：board中小于row的那些行都已经成功放置了皇后
    // 选择列表：第row行的所有列都是放置皇后的选择
    // 结束条件：row超过board的最后一行，说明棋盘放满了
    void backtrack(String[] board, int row){
        // 触发结束条件
        if (row == board.length){

        }
    }
}
